package com.example.algorithm.backtracing;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。
 * 请返回所有可行解 s 中最长长度。
 * <p>
 * 示例 1：
 * 输入：arr = ["un","iq","ue"]
 * 输出：4
 * 解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。
 * <p>
 * 示例 2：
 * 输入：arr = ["cha","r","act","ers"]
 * 输出：6
 * 解释：可能的解答有 "chaers" 和 "acters"。
 * <p>
 * 示例 3：
 * 输入：arr = ["abcdefghijklmnopqrstuvwxyz"]
 * 输出：26
 * <p>
 * 提示：
 * <p>
 * 1 <= arr.length <= 16
 * 1 <= arr[i].length <= 26
 * arr[i] 中只含有小写英文字母
 */
public class Leetcode1239_MaxLength {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        // "un","iq","ue"     "cha","r","act","ers"
//        list.add("cha");
//        list.add("act");
//        list.add("ers");
        list.add("will");
        System.out.println(new Solution().maxLength(list));
//        System.out.println(Integer.toBinaryString(4196608));

    }

    static class Solution {
        private int count = 0;

        /**
         * 回溯法:
         * 由于只关心某个字符是否出现，而不关心某个字符在原字符串的位置，因此可以将字符串使用 int 进行表示；
         *
         * 剪枝策略:
         * 预处理掉「本身具有重复字符」的无效字符串，并去重；
         * 然后使用位运算两两判断两个字符串是否有相同的字符
         * 没有重复的则依次合并
         *
         * @param arr
         * @return
         */
        public int maxLength(List<String> arr) {

            // 首先用位图将不含重复字符的字符串从arr中挑选出来
            List<Integer> strs = getNoRepetitiveIntStrings(arr);
            strs.forEach(e -> System.out.println(e));

            backtrace(strs, 0, 0);

            return count;
        }

        /**
         * 得到不重复的使用位图表示的字符串list
         * @param arr
         * @return
         */
        private List<Integer> getNoRepetitiveIntStrings(List<String> arr) {
            // 首先用位图将不含重复字符的字符串从arr中挑选出来
            // 因为arr中的每一个字符串只有26个小写字母且 len <= 26。所以位图用int(32位)足够了
            List<Integer> strs = new ArrayList<>(); // 使用位图(int)表示不含重复字符的字符串
            for (String s : arr) {
                int str = 0; // 使用位图表示的字符串(低26位为1表示对应的字符在该字符串中)
                for (int i = 0; i < s.length(); i++) {
                    int d = s.charAt(i) - 'a'; //
                    if (((str >> d) & 1) != 0) { // 判断是否存在了重复的字符
                        str = 0;
                        break; // 有重复的字符跳过这个字符串
                    }
                    str = str | (1 << d); // 将字符对应的位置置为1(将字符加入到用位图表示的字符串中)
                }
                // 一个字符串遍历完了，且没有重复的字符串，则加入到集合中
                if (str != 0) {
                    strs.add(str);
                }
            }
            return strs;
        }

        /**
         * @param strs 使用位图表示的字符串list
         * @param pos  list的索引
         * @param str  单个用位图表示的字符串
         */
        private void backtrace(List<Integer> strs, int pos, int str) {
            if (strs.size() == pos) { // 遍历到了最后一个字符串，应该结束了
                count = Math.max(count, Integer.bitCount(str));
                return;
            }

            if ((str & strs.get(pos)) == 0) { // 两个字符不存在一样的字符
                // str | strs.get(pos) 表示两个字符串进行合并
                backtrace(strs, pos + 1, str | strs.get(pos));
            }

            backtrace(strs,pos + 1, str); // 两个字符串存在相同的字符则要尝试下一个

        }
    }
}
